package LeetCode.exercise;

import java.util.Arrays;

public class LC_27 {
    public static void main(String[] args) {
        int[] nums ={0,1,2,2,3,0,4,2};
        int val = 2;
        int res = removeElement1(nums,val);
        System.out.println(res + " " + Arrays.toString(nums));

    }
    public static int removeElement(int[] nums, int val) {
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == val){
                nums[i] = 0;
                count++;
            }
        }
        for(int i = 0; i < nums.length - 1; i++){
            for(int j = 0; j < nums.length - i - 1; j++){
                if(nums[j] < nums[j+1]){
                    nums[j] = nums[j] + nums[j+1];
                    nums[j+1] = nums[j] - nums[j+1];
                    nums[j] = nums[j] - nums[j+1];
                }
            }
        }
        return nums.length - count;
    }
    public static int removeElement1(int[] nums, int val) { //双指针改进
        int left = 0;//左指针
        for (int right = 0; right < nums.length; right++){//右指针从最左端开始直到数组最后
            if (nums[right] != val){ //如果右指针指向的元素不是目标值
                if(nums[right] != nums[left]) { //并且左右指针指向的元素不相等
                    nums[right] = nums[right] + nums[left]; //在不使用额外空间的情况下
                    nums[left] = nums[right] - nums[left];  //交换左右指针所指的元素
                    nums[right] = nums[right] - nums[left]; //循环交换后目标值会被移到最后
                }
                left++; //如果右指针指向的元素不是目标值,左右指针同时后移
            }  // 否则左指针不动，右指针后移
        }
        return left; //最后左指针的下标即为删去目标值后数组的长度
    }
}
